package 链表;

/**
 * 19. 删除链表的倒数第 N 个结点
 *
 * 思路：找出待删除链表的前驱节点，然后将该节点的next指针指向待删除节点的下一个节点即可
 *  对于需要使用前驱节点的链表，可以定义一个辅助节点指向头节点，这样前驱节点就是辅助节点，
 *
 * 标准解答：双指针法：
 * 使用两个指针 fast 和 slow，初始时都指向链表的头节点。
 * 先让 fast 指针向前移动 n 步，使得 fast 和 slow 之间相隔 n 个节点。
 * 然后同时移动 fast 和 slow，直到 fast 指向链表的末尾。
 * 此时 slow 指向倒数第 n+1 个节点，删除 slow.next 即可。
 *
 * 虚拟头节点：
 * 使用虚拟头节点 dummy 简化边界处理，避免单独处理删除头节点的情况。
 */
public class L_19 {

    // 基本方法：两次遍历链表，找出待删除节点的前置节点
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        //1: 定义一个辅助节点
        ListNode dummy=new ListNode(-1);
        dummy.next=head;

        ListNode pre = dummy;
        ListNode cur = head;
        // 计算链表的长度
        int count=0;
        while (head!=null){
            count++;
            head = head.next;
        }
        // 获取待删除节点的前驱节点
        int index=count-n;
        for (int i = 0; i < index; i++) {
            pre = cur;
            cur = cur.next;
        }
        pre.next=cur.next;
        return dummy.next;
    }

    /**
     * 删除链表的倒数第 N 个节点
     * @param head 链表的头节点
     * @param n 倒数第 N 个节点
     * @return 删除后的链表头节点
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建虚拟头节点，简化边界处理
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 初始化快慢指针
        ListNode fast = dummy;
        ListNode slow = dummy;

        // 快指针先移动 n 步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // 同时移动快慢指针，直到快指针到达链表末尾
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 删除倒数第 n 个节点
        slow.next = slow.next.next;

        // 返回链表头节点
        return dummy.next;
    }



    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val,ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
